package cn.zzf.algs.note.base.sort;

import cn.zzf.algs.note.base.util.SortUtil;

/**
 * 插入排序改进版本，使用移动替代元素交换，同时先找出最小元素
 * @author GaoFeng2017
 * @date 2020/6/23 10:32
 */
public class InsertionV2Sort implements Sort {

    @Override
    public void sort(Comparable[] elements) {
        for (int i = 1; i < elements.length; i++) {
            int j = i - 1;;
            while (j >= 0 && SortUtil.less(elements[i], elements[j])) {
                j--;
            }
            this.rightShift(elements, j + 1, i);
        }
    }


    private void rightShift(Comparable[] elements,  int startPos, int  endPos) {

        if (endPos == startPos) {
            return;
        }

        if (endPos - startPos == 1) {
            SortUtil.exchange(elements, startPos, startPos + 1);
            return;
        }

        // 获取最后一个元素，腾出位置给较大元素进行移动
        Comparable currentElement = elements[endPos];

        for (int i = endPos; i > startPos; i--) {
            elements[i] = elements[i - 1];
        }

        // 2 3 4 1 -> 2 2 3 4 -> 1 2 3 4
        // 纸牌，10 J Q K，插入 9，将10 J Q K拼接到9后面，相比于两两交换，减少了访问数组的次数
        // 较大元素移动后，将最后一个元素插入到腾出的位置中
        elements[startPos] = currentElement;

    }

}
